import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main41 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt() ;
        int m = scan.nextInt() ;
        int[] arrV = new int[n+1] ; 
        int[] arrW = new int[n+1] ; 
        for(int i=0 ; i < n ; i ++){
            arrV[i+1] = scan.nextInt() ;
            arrW[i+1] = scan.nextInt() ;
        }
        int[][] dp = new int[n+1][m+1];
        for(int i=1 ; i <= n ; i ++){
            for(int j=1 ; j <= m; j ++){
               dp[i][j] = dp[i-1][j] ;
               if(j >= arrV[i]){
                dp[i][j] = Math.max(dp[i][j] , dp[i-1][j-arrV[i]] + arrW[i]);
               }
            }
        }
       System.out.println(dp[n][m]);  
       dp = new int[n+1][m+1] ; 
       for(int i=1 ; i <= m ; i ++){
          dp[0][i] = -1 ; 
       }
       for(int i=1 ; i <= n ; i ++){
        dp[i][0] = 0 ;
       }
       for(int i=1 ; i <= n ; i ++){
        for(int j=1 ; j <= m ; j ++) {
           dp[i][j] = dp[i-1][j] ; 
           if(j >= arrV[i] && dp[i-1][j-arrV[i]] != -1){
            dp[i][j] = Math.max(dp[i][j] , arrW[i] + dp[i-1][j-arrV[i]]);
           }
        }
       }
       System.out.println(dp[n][m]) ; 
    }
}